//
//  LinkList.swift
//  PlayData
//
//  Created by 冯琰琰 on 2022/3/18.
//

import Foundation


public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

class Solution {
    /**
     * 61. 旋转链表
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     */
    func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
        if head == nil || head?.next == nil || k == 0 {
            return head
        }
        var n = 1
        var header = head
        while header?.next != nil {
            header = header?.next
            n += 1
        }
        header?.next = head
        var dis = n - k % n
        while dis > 0 {
            dis -= 1
            header = header?.next
        }
        let ret = header?.next
        header?.next = nil
        return ret
    }
    
    /**
     * 92. 反转链表 II
     */
    func reverseBetween2(_ head: ListNode?, _ left: Int, _ right: Int) -> ListNode? {
        // 因为头指针可能会变化 设置一个虚拟头 就不用做判断了
        let dummyNode:ListNode? = ListNode(-1)
        dummyNode?.next = head
        
        //左侧的前驱节点
        var pre_left = dummyNode
        for _ in 0..<(left - 1) {
            pre_left = pre_left?.next
        }
        
        //右侧的节点
        var right_node = pre_left
        for _ in 0 ..< (right - left + 1) {
            right_node = right_node?.next
        }
        
        let left_nod = pre_left?.next
        let succ_right = right_node?.next
        
        // 断开右节点
        pre_left?.next = nil
        right_node?.next = nil
        //反转left_node
        var cur_nod = left_nod
        var pre_cur_node:ListNode? = nil
        
        while cur_nod != nil {
            let c_next = cur_nod?.next
            cur_nod?.next = pre_cur_node
            pre_cur_node = cur_nod
            cur_nod = c_next
        }
        
        pre_left?.next = right_node
        left_nod?.next = succ_right
        
        return dummyNode?.next
    }
    
    /**
     * 141. 环形链表
     */
        
    func hasCycle(_ head: ListNode?) -> Bool {
        if head == nil || head?.next == nil {return false}
        var fast = head
        var slow = head
        while fast != nil {
            fast = fast?.next?.next
            slow = slow?.next
            if fast === slow {
                return true
            }
        }
        return false
    }
    /**
     * 142. 环形链表 II
     */
    func detectCycle(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {return nil}
        var header = head
        var list:Array<ListNode> = []
        while header != nil {
            let ret = list.contains { node in
                 node === header
            }
            if ret {
                return header
            }
            list.append(header!)
            header = header?.next
        }
        return nil
    }
    
    /**
     * 2. 两数相加
     */
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        
        var header1 = l1
        var header2 = l2
        
        var carry = 0;
        var ret:ListNode? = ListNode()
        let header = ret
        while  header1 != nil || header2 != nil {
         
            let one = header1 == nil ? 0 : (header1?.val)!
            let two = header2 == nil ? 0 : (header2?.val)!
            
            let val = (one + two + carry) % 10
            let temp:ListNode? = ListNode()
            temp?.val = val
            ret?.next = temp
            ret = temp
            
            carry = (one + two + carry) / 10
            
            header1 = header1?.next
            header2 = header2?.next
        }
        if carry == 1 {
            let temp:ListNode? = ListNode()
            temp?.val = 1
            ret?.next = temp
            ret = temp
            carry = 0
        }
        return header?.next
    }
    
    /**
     * 445. 两数相加 II
     */
    func addTwoNumbers01(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        
        var header1 = l1
        var header2 = l2
        var headerStack1 = [Int]()
        var headerStack2 = [Int]()
        while header1 != nil {
            headerStack1.append(header1!.val)
            header1 = header1?.next
        }
        while header2 != nil {
            headerStack2.append(header2!.val)
            header2 = header2?.next
        }
        var carry = 0;
        var ret:ListNode? = ListNode()
        while headerStack1.count > 0 || headerStack2.count > 0 {
            let val1 = headerStack1.count > 0 ? (headerStack1.popLast())! : 0
            let val2 = headerStack2.count > 0 ? (headerStack2.popLast())! : 0
            let val = (val1 + val2 + carry) % 10
            carry = (val1 + val2 + carry) / 10
            ret?.val = val
            let temp:ListNode? = ListNode()
            temp?.next = ret
            ret = temp
        }
        if carry > 0 {
            ret?.val = carry
            let temp:ListNode? = ListNode()
            temp?.next = ret
            ret = temp
        }
        
        return ret?.next
    }
}

